#include <stdio.h>
#include <stdlib.h>  // 用于 malloc/free

// 扩展欧几里得算法：计算 ax + by = gcd(a,b)，返回gcd，同时输出x（模逆）
// 若a和m互质，x的正模m结果即为a在模m下的逆元
int extend_gcd(int a, int m, int *x, int *y) {
    if (m == 0) {
        *x = 1;
        *y = 0;
        return a;  // gcd(a,0) = a
    }
    int gcd = extend_gcd(m, a % m, y, x);
    *y -= (a / m) * (*x);
    return gcd;
}

// 模逆函数（对应Python的 modular_inverse）：计算b在模m下的逆元
// 前提：b和m互质（原Python代码未处理不互质情况，此处保持一致）
int modular_inverse(int b, int m) {
    int x, y;
    int gcd = extend_gcd(b, m, &x, &y);

    // 若gcd != 1，说明b和m不互质，无模逆（原Python代码未处理，此处返回-1提示错误）
    if (gcd != 1) {
        fprintf(stderr, "错误：%d 和 %d 不互质，无模逆！\n", b, m);
        return -1;
    }

    // 将x转换为正模m的结果（避免负逆元）
    return (x % m + m) % m;
}

// 中国剩余定理（CRT）：a_array是余数数组，m_array是模数数组，n是数组长度
// 前提：模数m_array中元素两两互质（原Python代码假设，此处保持一致）
int crt(int *a_array, int *m_array, int n) {
    int m_pi = 1;
    // 计算所有模数的乘积 m_pi = m1*m2*...*mn
    for (int i = 0; i < n; i++) {
        m_pi *= m_array[i];
    }

    int x = 0;
    for (int i = 0; i < n; i++) {
        int a = a_array[i];
        int m = m_array[i];
        int b = m_pi / m;  // b = m_pi / mi（因模数互质，b和m互质）

        // 计算b在模m下的逆元
        int inv_b = modular_inverse(b, m);
        if (inv_b == -1) {
            return -1;  // 无模逆时返回错误
        }

        // 累加：x += a * b * inv_b
        x += a * b * inv_b;
    }

    // 返回x mod m_pi（确保结果在[0, m_pi-1]范围内）
    return x % m_pi;
}

int main() {
    // 测试用例：对应Python的 crt([2,3,2], [3,5,7])
    int a_array[] = {2, 3, 2};
    int m_array[] = {3, 5, 7};
    int n = sizeof(a_array) / sizeof(a_array[0]);  // 数组长度（3）

    int result = crt(a_array, m_array, n);
    if (result != -1) {
        printf("CRT结果：%d\n", result);  // 预期输出：23
        printf("验证：%d mod 3 = %d（期望2）\n", result, result % 3);
        printf("验证：%d mod 5 = %d（期望3）\n", result, result % 5);
        printf("验证：%d mod 7 = %d（期望2）\n", result, result % 7);
    }

    return 0;
}